"""
动态规划算法

问题描述：
    动态规划（Dynamic Programming, DP）是一种解决具有重叠子问题和最优子结构性质的
    优化问题的算法设计方法。它通过将复杂问题分解为更小的子问题，
    并存储子问题的解来避免重复计算，从而提高算法效率。

算法原理：
    动态规划的核心思想：
    1. 重叠子问题：问题可以分解为子问题，且子问题会被多次求解
    2. 最优子结构：问题的最优解包含子问题的最优解
    3. 状态转移方程：描述问题状态之间关系的递推公式
    4. 边界条件：递推的起始状态

核心概念：
    - 状态定义：用变量描述问题的阶段和状态
    - 状态转移：从一个状态转移到另一个状态的规律
    - 备忘录化：存储已计算的子问题结果
    - 自底向上vs自顶向下：两种不同的实现方式

应用场景：
    动态规划广泛应用于：
    - 背包问题
    - 最短路径问题
    - 序列比对问题
    - 投资决策问题
    - 资源分配问题

作者：斯黄
日期：2025年3月4日
"""

import numpy as np
import matplotlib.pyplot as plt
import time
from functools import lru_cache

# 1. 经典斐波那契数列问题
class FibonacciDP:
    def __init__(self):
        self.memo = {}
    
    def fib_recursive(self, n):
        """递归解法（指数时间复杂度）"""
        if n <= 1:
            return n
        return self.fib_recursive(n-1) + self.fib_recursive(n-2)
    
    def fib_memoization(self, n):
        """记忆化递归（自顶向下）"""
        if n in self.memo:
            return self.memo[n]
        
        if n <= 1:
            result = n
        else:
            result = self.fib_memoization(n-1) + self.fib_memoization(n-2)
        
        self.memo[n] = result
        return result
    
    def fib_tabulation(self, n):
        """动态规划（自底向上）"""
        if n <= 1:
            return n
        
        dp = [0] * (n + 1)
        dp[0], dp[1] = 0, 1
        
        for i in range(2, n + 1):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[n]
    
    def fib_optimized(self, n):
        """空间优化的动态规划"""
        if n <= 1:
            return n
        
        prev2, prev1 = 0, 1
        for i in range(2, n + 1):
            current = prev1 + prev2
            prev2, prev1 = prev1, current
        
        return prev1

# 2. 背包问题
class KnapsackDP:
    def knapsack_01(self, weights, values, capacity):
        """0-1背包问题"""
        n = len(weights)
        # dp[i][w] 表示前i个物品在容量为w时的最大价值
        dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            for w in range(capacity + 1):
                # 不选择第i个物品
                dp[i][w] = dp[i-1][w]
                
                # 如果能选择第i个物品
                if weights[i-1] <= w:
                    dp[i][w] = max(dp[i][w], 
                                 dp[i-1][w-weights[i-1]] + values[i-1])
        
        # 回溯找出选择的物品
        selected = []
        w = capacity
        for i in range(n, 0, -1):
            if dp[i][w] != dp[i-1][w]:
                selected.append(i-1)
                w -= weights[i-1]
        
        return dp[n][capacity], selected[::-1]
    
    def knapsack_unbounded(self, weights, values, capacity):
        """无界背包问题（完全背包）"""
        dp = [0] * (capacity + 1)
        
        for w in range(1, capacity + 1):
            for i in range(len(weights)):
                if weights[i] <= w:
                    dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
        
        return dp[capacity]

# 3. 最长公共子序列问题
class LCSDP:
    def lcs_length(self, text1, text2):
        """计算最长公共子序列长度"""
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        return dp[m][n], dp
    
    def lcs_string(self, text1, text2):
        """获取最长公共子序列字符串"""
        length, dp = self.lcs_length(text1, text2)
        
        # 回溯构建LCS字符串
        lcs = []
        i, j = len(text1), len(text2)
        
        while i > 0 and j > 0:
            if text1[i-1] == text2[j-1]:
                lcs.append(text1[i-1])
                i -= 1
                j -= 1
            elif dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
        
        return ''.join(reversed(lcs))

# 4. 最短路径问题（Floyd算法）
class ShortestPathDP:
    def floyd_warshall(self, graph):
        """Floyd-Warshall算法求所有节点间最短路径"""
        n = len(graph)
        # 初始化距离矩阵
        dist = [[float('inf')] * n for _ in range(n)]
        
        # 设置直接相邻的距离和自身距离
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif graph[i][j] != 0:
                    dist[i][j] = graph[i][j]
        
        # 动态规划更新最短距离
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        return dist

# 5. 投资决策问题
class InvestmentDP:
    def max_profit(self, prices, fee=0):
        """股票买卖最大利润（含手续费）"""
        if not prices:
            return 0
        
        n = len(prices)
        # hold[i]: 第i天持有股票时的最大利润
        # sold[i]: 第i天不持有股票时的最大利润
        hold = -prices[0]
        sold = 0
        
        for i in range(1, n):
            new_hold = max(hold, sold - prices[i])
            new_sold = max(sold, hold + prices[i] - fee)
            hold, sold = new_hold, new_sold
        
        return sold

# 演示和性能对比
def demonstrate_fibonacci():
    print("=== 斐波那契数列不同实现方法对比 ===")
    fib = FibonacciDP()
    
    test_numbers = [10, 20, 30, 35]
    
    for n in test_numbers:
        print(f"\n计算 Fibonacci({n}):")
        
        # 记忆化递归
        start_time = time.time()
        result_memo = fib.fib_memoization(n)
        time_memo = time.time() - start_time
        
        # 动态规划
        start_time = time.time()
        result_dp = fib.fib_tabulation(n)
        time_dp = time.time() - start_time
        
        # 空间优化DP
        start_time = time.time()
        result_opt = fib.fib_optimized(n)
        time_opt = time.time() - start_time
        
        print(f"记忆化递归: {result_memo} (时间: {time_memo:.6f}s)")
        print(f"动态规划: {result_dp} (时间: {time_dp:.6f}s)")
        print(f"空间优化DP: {result_opt} (时间: {time_opt:.6f}s)")
        
        # 对于小的n，也测试纯递归（注意：大的n会很慢）
        if n <= 35:
            fib.memo = {}  # 重置记忆化缓存
            start_time = time.time()
            result_rec = fib.fib_recursive(n)
            time_rec = time.time() - start_time
            print(f"纯递归: {result_rec} (时间: {time_rec:.6f}s)")

def demonstrate_knapsack():
    print("\n=== 背包问题演示 ===")
    knapsack = KnapsackDP()
    
    # 0-1背包问题示例
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    capacity = 8
    
    max_value, selected = knapsack.knapsack_01(weights, values, capacity)
    
    print("0-1背包问题:")
    print(f"物品重量: {weights}")
    print(f"物品价值: {values}")
    print(f"背包容量: {capacity}")
    print(f"最大价值: {max_value}")
    print(f"选择的物品索引: {selected}")
    
    selected_weights = [weights[i] for i in selected]
    selected_values = [values[i] for i in selected]
    print(f"选择的物品重量: {selected_weights} (总重量: {sum(selected_weights)})")
    print(f"选择的物品价值: {selected_values} (总价值: {sum(selected_values)})")
    
    # 无界背包问题
    max_value_unbounded = knapsack.knapsack_unbounded(weights, values, capacity)
    print(f"\n无界背包最大价值: {max_value_unbounded}")

def demonstrate_lcs():
    print("\n=== 最长公共子序列演示 ===")
    lcs = LCSDP()
    
    text1 = "ABCDGH"
    text2 = "AEDFHR"
    
    length, dp = lcs.lcs_length(text1, text2)
    lcs_str = lcs.lcs_string(text1, text2)
    
    print(f"字符串1: {text1}")
    print(f"字符串2: {text2}")
    print(f"最长公共子序列长度: {length}")
    print(f"最长公共子序列: {lcs_str}")
    
    # 可视化DP表
    print("\nDP表格:")
    print("    ", " ".join(f"{c:>2}" for c in " " + text2))
    for i, row in enumerate(dp):
        char = " " if i == 0 else text1[i-1]
        print(f"{char:>2}:", " ".join(f"{val:>2}" for val in row))

def demonstrate_shortest_path():
    print("\n=== 最短路径问题演示 ===")
    
    # 图的邻接矩阵表示（0表示无直接连接）
    graph = [
        [0, 5, 0, 10],
        [0, 0, 3, 0],
        [0, 0, 0, 1],
        [0, 0, 0, 0]
    ]
    
    shortest_path = ShortestPathDP()
    distances = shortest_path.floyd_warshall(graph)
    
    print("原始图的邻接矩阵:")
    for row in graph:
        print([val if val != 0 else "∞" for val in row])
    
    print("\n所有节点间最短距离:")
    for i, row in enumerate(distances):
        for j, dist in enumerate(row):
            if dist == float('inf'):
                print(f"节点{i}到节点{j}: ∞")
            else:
                print(f"节点{i}到节点{j}: {dist}")

def demonstrate_investment():
    print("\n=== 投资决策问题演示 ===")
    
    # 模拟股票价格
    prices = [7, 1, 5, 3, 6, 4, 8, 2]
    fee = 2
    
    investment = InvestmentDP()
    max_profit = investment.max_profit(prices, fee)
    
    print(f"股票价格序列: {prices}")
    print(f"交易手续费: {fee}")
    print(f"最大利润: {max_profit}")

def visualize_dp_problems():
    """可视化动态规划问题"""
    fig, axes = plt.subplots(2, 2, figsize=(15, 10))
    
    # 1. 斐波那契数列增长
    fib = FibonacciDP()
    n_values = range(1, 21)
    fib_values = [fib.fib_optimized(n) for n in n_values]
    
    axes[0, 0].plot(n_values, fib_values, 'bo-')
    axes[0, 0].set_title('斐波那契数列增长')
    axes[0, 0].set_xlabel('n')
    axes[0, 0].set_ylabel('Fibonacci(n)')
    axes[0, 0].grid(True)
    
    # 2. 背包问题价值分布
    knapsack = KnapsackDP()
    capacities = range(1, 21)
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    
    max_values = []
    for cap in capacities:
        max_val, _ = knapsack.knapsack_01(weights, values, cap)
        max_values.append(max_val)
    
    axes[0, 1].plot(capacities, max_values, 'ro-')
    axes[0, 1].set_title('背包容量vs最大价值')
    axes[0, 1].set_xlabel('背包容量')
    axes[0, 1].set_ylabel('最大价值')
    axes[0, 1].grid(True)
    
    # 3. LCS长度热力图
    lcs = LCSDP()
    text1 = "ABCDGH"
    text2 = "AEDFHR"
    _, dp = lcs.lcs_length(text1, text2)
    
    im = axes[1, 0].imshow(dp, cmap='YlOrRd')
    axes[1, 0].set_title('LCS动态规划表')
    axes[1, 0].set_xlabel('字符串2索引')
    axes[1, 0].set_ylabel('字符串1索引')
    fig.colorbar(im, ax=axes[1, 0])
    
    # 4. 算法复杂度对比
    sizes = [5, 10, 15, 20, 25, 30]
    dp_times = []
    memo_times = []
    
    for n in sizes:
        fib = FibonacciDP()
        
        # DP时间
        start = time.time()
        fib.fib_tabulation(n)
        dp_times.append(time.time() - start)
        
        # 记忆化时间
        start = time.time()
        fib.fib_memoization(n)
        memo_times.append(time.time() - start)
    
    axes[1, 1].plot(sizes, dp_times, 'g-o', label='动态规划')
    axes[1, 1].plot(sizes, memo_times, 'r-s', label='记忆化递归')
    axes[1, 1].set_title('算法性能对比')
    axes[1, 1].set_xlabel('问题规模')
    axes[1, 1].set_ylabel('运行时间(秒)')
    axes[1, 1].legend()
    axes[1, 1].grid(True)
    
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    # 运行所有演示
    demonstrate_fibonacci()
    demonstrate_knapsack()
    demonstrate_lcs()
    demonstrate_shortest_path()
    demonstrate_investment()
    
    # 可视化
    visualize_dp_problems() 